#最小覆盖子串
from collections import defaultdict
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if len(s) < len(t):
            return ""

        # 定义哈希表，用于记录窗口内字符和目标字符串字符
        hashtable_s = defaultdict(int)
        hashtable_t = defaultdict(int)

        # 初始化目标字符串的哈希表
        for char in t:
            hashtable_t[char] += 1

        # 定义滑动窗口的起始和结束
        start, end = 0, 0
        min_len = float('inf')
        min_start = 0
        have = 0
        total = len(t)

        # 滑动窗口进行遍历
        while end < len(s):
            # 扩大窗口，添加字符到哈希表中
            char_end = s[end]
            hashtable_s[char_end] += 1

            # 如果当前字符满足了目标字符的数量，增加已满足的数量
            if char_end in hashtable_t and hashtable_s[char_end] <= hashtable_t[char_end]:
                have += 1

            # 当所有字符都满足时，尝试缩小窗口
            while have == total:
                # 更新最小窗口
                if end - start + 1 < min_len:
                    min_len = end - start + 1
                    min_start = start

                # 尝试缩小窗口，从左边移动
                char_start = s[start]
                hashtable_s[char_start] -= 1
                if char_start in hashtable_t and hashtable_s[char_start] < hashtable_t[char_start]:
                    have -= 1
                start += 1

            # 移动窗口的右端
            end += 1

        # 返回最小覆盖子串
        if min_len == float('inf'):
            return ""
        else:
            return s[min_start:min_start + min_len]

